package com.zyk.leetcode;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
 *
 * @author zhangsan
 * @date 2021/4/2 16:55
 */
public class J32 {


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    public static int[] levelOrder01(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        int[] ans = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    public static List<List<Integer>> levelOrder1(TreeNode root) {
        // 层级便利
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> levelAns = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        TreeNode nextEnd = root;
        TreeNode curEnd = root;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            levelAns.add(cur.val);
            if (cur.left != null) {
                nextEnd = cur.left;
                queue.add(cur.left);
            }
            if (cur.right != null) {
                nextEnd = cur.right;
                queue.add(cur.right);
            }
            if (curEnd == cur) {
                curEnd = nextEnd;
                ans.add(levelAns);
                levelAns = new ArrayList<>();
            }
        }
        return ans;
    }

    // 层级遍历的基础上, 改成之字形遍历

    /**
     * https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
     */
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 层级便利
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<Integer> levelAns;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        TreeNode cur;
        while (!queue.isEmpty()) {
            levelAns = new LinkedList<>();
            for (int i = queue.size(); i > 0; i--) {
                cur = queue.poll();
                // 偶数层,左向右,往后添
                if (ans.size() % 2 == 0) {
                    levelAns.addLast(cur.val);
                } else {
                    // 奇数层,右向左, 往左添, 最先进取得在最右边
                    levelAns.addFirst(cur.val);
                }
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            ans.add(levelAns);
        }
        return ans;
    }

}
